#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>

using namespace std;

/**
 * @brief 827. 最大人工岛
 * https://leetcode.cn/problems/making-a-large-island/
 */
class Solution {
public:
    /**
     * @brief 该算法速度更快（改造一下最大陆地面积解法即可）！
     * 先遍历所有格子得到各个岛屿的面积，记录岛屿部分的索引值。
     * 使用哈希表记录索引值对应的岛屿面积。
     * 填海时检测周围格子的索引值，取出面积进行计算。
     */
    int largestIsland(vector<vector<int>>& grid) {
        int nr = grid.size();
        int nc = grid[0].size();
        int maxSoFar = 0; // 这样可以处理全为陆地的情况
        vector<vector<int>> visited(nr, vector<int>(nc, 0));
        unordered_map<int, int> areaMap;
        int id = 0;
        for (int i = 0; i < nr; i++) {
            for (int j = 0; j < nc; j++) {
                if (visited[i][j] == 0 && grid[i][j] == 1) {
                    int area = 0;
                    DFS(grid, visited, i, j, ++id, area);
                    maxSoFar = max(maxSoFar, area);
                    areaMap[id] = area;
                }
            }
        }
        for (int i = 0; i < nr; i++) {
            for (int j = 0; j < nc; j++) {
                if (visited[i][j] == 0) {
                    set<int> ids;
                    if (i-1 >= 0 && visited[i-1][j] != 0) ids.insert(visited[i-1][j]);
                    if (i+1 < nr && visited[i+1][j] != 0) ids.insert(visited[i+1][j]);
                    if (j-1 >= 0 && visited[i][j-1] != 0) ids.insert(visited[i][j-1]);
                    if (j+1 < nc && visited[i][j+1] != 0) ids.insert(visited[i][j+1]);
                    int sumArea = 1;
                    for (auto& id_ : ids) {
                        sumArea += areaMap[id_];
                    }
                    maxSoFar = max(maxSoFar, sumArea);
                }
            }
        }
        return maxSoFar;
    }

    void DFS(vector<vector<int>>& grid, vector<vector<int>>& visited, int i, int j, int id, int& area) {
        area += 1;
        visited[i][j] = id;
        grid[i][j] = 0;
        int nr = grid.size();
        int nc = grid[0].size();
        if (i-1 >= 0 && grid[i-1][j] == 1 && visited[i-1][j] == 0) DFS(grid, visited, i-1, j, id, area);
        if (i+1 < nr && grid[i+1][j] == 1 && visited[i+1][j] == 0) DFS(grid, visited, i+1, j, id, area);
        if (j-1 >= 0 && grid[i][j-1] == 1 && visited[i][j-1] == 0) DFS(grid, visited, i, j-1, id, area);
        if (j+1 < nc && grid[i][j+1] == 1 && visited[i][j+1] == 0) DFS(grid, visited, i, j+1, id, area);
    }

/**
 * 朴素思路：一旦遇到一个海洋格子，将其填为陆地并进行 DFS。
 * 速度可能太慢，函数调用太多。
 */
    // int largestIsland(vector<vector<int>>& grid) {
    //     int nr = grid.size();
    //     if (nr == 0) return 0;
    //     int nc = grid[0].size();

    //     // 进行填海
    //     int maxArea = 0;
    //     for (int r = 0; r < nr; ++r) {
    //         for (int c = 0; c < nc; ++c) {
    //             if (grid[r][c] == 0) {
    //                 grid[r][c] = 1;
    //                 int areaSofar = 0;
    //                 vector<vector<int>> visited(nr, vector<int>(nc, 0));
    //                 dfs(grid, visited, r, c, areaSofar);
    //                 maxArea = max(maxArea, areaSofar);
    //                 grid[r][c] = 0;
    //             }
    //         }
    //     }
    //     // 查看是否全为陆地
    //     int wholeArea = 0;
    //     for (int r = 0; r < nr; ++r) {
    //         for (int c = 0; c < nc; ++c) {
    //             if (grid[r][c] == 1) wholeArea++;
    //         }
    //     }
    //     if (wholeArea != (nr*nc)) wholeArea = 0;
    //     return max(maxArea, wholeArea);
    // }

    // // Assumption: [r, c] is a valid location.
    // void dfs(const vector<vector<int>>& grid, vector<vector<int>>& visited, int r, int c, int& area) {
    //     if (!grid[r][c] == 1) return;
    //     int nr = grid.size();
    //     int nc = grid[0].size();
    //     area++;
    //     visited[r][c] = 2;  // 2 means visited
    //     if (r-1>=0 && visited[r-1][c] == 0 && grid[r-1][c] == 1) dfs(grid, visited, r-1, c, area);
    //     if (r+1<nr && visited[r+1][c] == 0 && grid[r+1][c] == 1) dfs(grid, visited, r+1, c, area);
    //     if (c-1>=0 && visited[r][c-1] == 0 && grid[r][c-1] == 1) dfs(grid, visited, r, c-1, area);
    //     if (c+1<nc && visited[r][c+1] == 0 && grid[r][c+1] == 1) dfs(grid, visited, r, c+1, area);
    // }
};

int main() {
    Solution sol;
    vector<vector<int>> grid{{1,1},{1,1}};
    std::cout << sol.largestIsland(grid) << std::endl;
    return 0;
}
